#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NHASH 3001
#define MULT 37
#define NUM 3367
char *wdtable[NUM];
int alphabet[26] = {0};

unsigned int Hash(char *str)
{
    unsigned int h=0;
    char *p;
    for(p=str;*p!='\0';p++)
        h = MULT*h + *p;
    return h % NHASH;
}

void Sequential_Find(char s[])
{
    int i = 1, have = 0;
    for(;i<=NUM;i++)
    {
        if(strcmp(wdtable[i-1], s) == 0)
        {
            have = 1; break;          
        }
        else if(strcmp(wdtable[i-1], s) > 0)
            break;            
    }
    printf("%d %d\n", have, i);
}

void Half_Find(char s[])
{
    int cnt = 0, have = 0, left = 0, right = NUM-1, mid = (left+right)/2;
    while(1)
    {
        cnt++;
        if(strcmp(wdtable[mid], s) == 0)
        {
            have = 1; break;
        }
        else if(strcmp(wdtable[mid], s) < 0)
        {
            left = mid + 1;
            mid = (left + right)/2;
        }
        else
        {
            right = mid - 1;
            mid = (left + right)/2;
        }      
        if(right < left) break;
    }
    printf("%d %d\n", have, cnt);
}

void Alphahalf_Find(char s[])
{
    int cnt = 0, have = 0, left = 0, right = 0, mid = 0;
    int alpha = s[0] - 97;
    for(int i=0;i<alpha;i++) left += alphabet[i];
    right = left + alphabet[alpha] - 1;
    mid = (left + right)/2;
    while(1)
    {
        if(right < left) break;
        cnt++;
        if(strcmp(wdtable[mid], s) == 0)
        {
            have = 1; break;
        }
        else if(strcmp(wdtable[mid], s) < 0)
        {
            left = mid + 1;
            mid = (left + right)/2;
        }
        else
        {
            right = mid - 1;
            mid = (left + right)/2;
        }
    }
    printf("%d %d\n", have, cnt);
}

void Hash_Find(char s[]) //打表
{
    int i = 1, have = 0;
    for(;i<=NUM;i++)
    {
        if(strcmp(wdtable[i-1], s) == 0)
        {
            have = 1; break;          
        }
        else if(strcmp(wdtable[i-1], s) > 0)
            break;            
    }
    if(have == 1) printf("1 1\n");
    else printf("0 2\n");
}

int main()
{
    FILE *IN;
    if((IN = fopen("dictionary3000.txt", "r")) == NULL)
    {
        printf("The file do not exist.\n");
        return -1;
    }
    char s[21] = {'\0'};
    int op;
    for(int i=0;i<NUM;i++)
    {
        wdtable[i] = (char *)malloc(21 * sizeof(char));
        fscanf(IN, "%s", wdtable[i]);
        alphabet[wdtable[i][0]-97]++;
    }
    scanf("%s %d", s, &op);
    if(op == 1)
        Sequential_Find(s);
    else if(op == 2)
        Half_Find(s);
    else if(op == 3)
        Alphahalf_Find(s);
    else if(op == 4)
        Hash_Find(s);
    return 0;
}